#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int left = 0;
        while (left < n - 2)
        {
            int right = n - 1;
            int mid = left + 1;
            while (mid < right)
            {
                if (nums[mid] + nums[left] + nums[right] > 0)
                {
                    right--;
                }
                else if (nums[mid] + nums[left] + nums[right] < 0)
                {
                    mid++;
                }
                else
                {
                    ret.push_back({ nums[left],nums[mid],nums[right] });
                    while (mid < right && (nums[mid] == nums[mid + 1]))
                    {
                        mid++;
                    }
                    mid++;
                }
            }
            left++;
            while (left < n - 2 && (nums[left - 1] == nums[left]))
            {
                left++;
            }
        }
        return ret;
    }
};

int main()
{
    Solution s;
    vector<int> v = { 0,0,0};
    s.threeSum(v);
    return 0;
}

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int i = nums.size() - 1;
        while (i > 2)
        {
            long long p = target - nums[i];
            int k = i - 1;
            while (k > 1)
            {
                int left = 0;
                int right = k - 1;
                while (left < right)
                {
                    if ((long long)nums[left] + nums[right] + nums[k] == p)
                    {
                        ret.push_back({ nums[left],nums[right],nums[k],nums[i] });
                        while (right > left && nums[right] == nums[right - 1])
                        {
                            right--;
                        }
                        right--;
                    }
                    else if ((long long)nums[left] + nums[right] + nums[k] < p)
                    {
                        left++;
                    }
                    else
                    {
                        right--;
                    }
                }
                while (k > 1 && nums[k] == nums[k - 1])
                {
                    k--;
                }
                k--;
            }
            while (i > 2 && nums[i - 1] == nums[i])
            {
                i--;
            }
            i--;
        }
        return ret;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = 0;
        int sum = 0;
        int ret = INT_MAX;
        while (right < n)
        {
            sum += nums[right];
            while (sum >= target)
            {
                ret = min(right - left + 1, ret);
                sum -= nums[left++];
            }
            right++;
        }
        if (ret == INT_MAX)
        {
            return 0;
        }
        return ret;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int n = s.size();
        int left = 0;
        int right = 0;
        int ret = 0;
        while (right < n)
        {
            hash[s[right]]++;
            while (hash[s[right]] > 1)
            {
                hash[s[left++]]--;
            }
            ret = max(right - left + 1, ret);
            right++;
        }
        return ret;
    }
};

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        int left = 0;
        int right = 0;
        int n = nums.size();
        int zero = 0;
        while (right < n)
        {
            if (nums[right] == 0)
            {
                zero++;
                while (zero > k)
                {
                    if (nums[left] == 0)
                    {
                        zero--;
                    }
                    left++;
                }
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};